package org.everyday;

/**
 * @version v1.0.0
 * 创建时间：2022/7/26 15:52
 */
public class SkipList {
    double p = 0.25d;
    int MAX_LEVEL = 32;
    // 当前实际有效的最大层数
    private int levelSize;
    // 头结点
    Node head;

    public SkipList() {
        // 一开始啥也没
        levelSize = 0;
        // head指出32个next的节点
        head = new Node(-1, MAX_LEVEL);
    }

    private class Node{
        Integer value; //节点值
        Node[] next; // 节点在不同层的下一个节点

        public Node(Integer value,int size) { // 用size表示当前节点在跳表中索引几层
            this.value = value;
            this.next = new Node[size];
        }
    }

    public int randomLevel(){
        int level = 1;
        while (Math.random()<p && level<MAX_LEVEL){
            level ++ ;
        }
        return level;
    }

    public boolean search(int target) {
        Node headNode = head;
        // 从有效的顶层开始搜索
        for(int i = levelSize - 1; i >= 0; i--) {
            headNode = findClosest(headNode, i, target);
            if(headNode.next[i] != null && headNode.next[i].value == target) {
                return true;
            }
        }
        return false;
    }

    public void add(int num) {
        // 随机层
        int insertLevel = randomLevel();
        // 随机层对应的新节点
        Node newNode = new Node(num, insertLevel);
        Node headNode = head;
        // 最高层开始插入
        for(int levelIndex = levelSize - 1; levelIndex >= 0; levelIndex--) {
            headNode = findClosest(headNode, levelIndex, num);
            // 当前层<newNode要求的层数时,每一层均要进行插入操作
            // 如level=2时,只要求索引为0,1的层进行插入
            if(levelIndex < insertLevel) {
                if(headNode.next[levelIndex] == null) {
                    // 目标位置处为空直接接上
                    headNode.next[levelIndex] = newNode;
                }else {
                    // 否则就要进行标准插入操作
                    Node tmp = headNode.next[levelIndex];
                    headNode.next[levelIndex] = newNode;
                    newNode.next[levelIndex] = tmp;
                }
            }
        }
        // 此时有可能要更新curLevel
        if(insertLevel > levelSize) {
            for(int i = levelSize; i < insertLevel; i++) {
                head.next[i] = newNode;
            }
            levelSize = insertLevel;
        }
    }


    public boolean erase(int num) {
        Node headNode = head;
        boolean res = false;
        for (int levelIndex = levelSize-1; levelIndex >= 0; levelIndex--) {
            headNode = findClosest(headNode, levelIndex, num);
            if (headNode.next[levelIndex]!=null && headNode.next[levelIndex].value==num){
                headNode.next[levelIndex] = headNode.next[levelIndex].next[levelIndex];
                res = true;
            }
        }
        return res;
    }


    /**
     * 从curNode开始:
     * 寻找level层内最靠近target的左边节点(如target=6,5->6->7,停留在5;如target=6,5->7->8,停留在5)
     */
    private Node findClosest(Node node,int levelIndex,int target){
        while ((node.next[levelIndex])!=null && target >node.next[levelIndex].value){
            node = node.next[levelIndex];
        }
        return node;
    }

    public static void main(String[] args) {
        SkipList skipList = new SkipList();
        skipList.add(1);
        skipList.add(2);
        skipList.add(3);
        boolean search = skipList.search(3);
        System.out.println(search);
    }
}
